#ifndef REM_H
#define	REM_H

#ifdef	__cplusplus
extern "C" {
#endif

    void getInverse(mpz_t elem, mpz_t module, mpz_t* inverse) {
        mpz_t y, gcd;
        mpz_inits(y, gcd, *inverse, NULL);
        mpz_gcdext(gcd, y, *inverse, elem, module);
        //gmp_printf("(%Zd)(%Zd) + (%Zd)(%Zd) = %Zd \n", elem,y,module,*inverse,gcd);
        mpz_clears(y, gcd, NULL);
    }

    void chineseRemainder(int* modules, int* values, int numModules, mpz_t number) { //given the used modules and the computed values - determine exact value
        int i;
        mpz_t N;
        mpz_inits(N, number, NULL);
        mpz_set_si(N, 1L);
        for (i = 0; i < numModules; i++) {
            mpz_mul_si(N, N, (long) modules[i]);
        }
        for (i = 0; i < numModules; i++) {
            mpz_t N_i, n_i, inverse;
            mpz_inits(N_i, n_i, NULL);
            mpz_set_si(n_i, (long) modules[i]);
            mpz_cdiv_q(N_i, N, n_i);
            getInverse(n_i, N_i, &inverse);
            mpz_mul(N_i, N_i, inverse);
            mpz_mul_si(N_i, N_i, (long) values[i]);
            mpz_add(number, number, N_i);
            mpz_clears(N_i, n_i, inverse, NULL);
        }
        mpz_fdiv_r(number, number, N);
    }
#ifdef	__cplusplus
}
#endif

#endif	/* REM_H */